#ifndef __KMP__
#define __KMP__

#define kmpsearch(x) KMP::searchstring1(x)

namespace KMP{

	// naive method: return the index in the parent string (starting from 0)
	int searchstring0(string s, string keyword){
		int failurefunction[6]={0,0,1,2,3,1};
		for (int i=0;i<s.size();i++){///////i++ can be optimized here!!!
			for (int j=0;j<s.size();j++){
				if (s.at(i+j) == keyword.at(j)){
					if (keyword.size()==j+1){
						return i;
					}
				}else{
					break;
				}
			}
		}
		return -1;
	}

	// KMP method: return the index in the parent string (starting from 0)
	int searchstring1(string s, string keyword){
		int failurefunction[6]={0,0,1,2,3,1};
		int steps=0;
		for (int i=0;i<s.size();i=i+1+failurefunction[steps]){
			for (int j=steps;j<s.size();j++){
				if (s.at(i+j) == keyword.at(j)){
					if (keyword.size()==j+1){
						return i;
					}
				}else{
					steps=j;
					break;
				}
			}
		}
		return -1;
	}

	// ababaa
	// 001231
	void getfailurefunction(string keyword, int in_ff[]){
		int ksize=keyword.size();
		in_ff[0] = 0;
		int t=0;
		for (int i=1; i<ksize; i++){
			while(t>0 && keyword[i]!=keyword[t]){
				//printf("%c %d %c %d\n", keyword[i], i, keyword[t], t);
				t=in_ff[t-1];//????
			}
			if (keyword[i] == keyword[t]){
				t++;
				in_ff[i] = t;
			}else{
				in_ff[i] = t;//??=0
			}
		}
	}

};





#endif